using System.Collections.Generic;
using System;
using Unity.Mathematics;

namespace Geometry
{
    public class QuadtreeTileAvailability
    {

        QuadtreeTilingScheme _tilingScheme;
        int _maximumLevel;
        QuadtreeNode[] _rootNodes = null;
        public QuadtreeTileAvailability(QuadtreeTilingScheme tilingScheme, int maximumLevel)
        {
            this._tilingScheme = tilingScheme;
            this._maximumLevel = maximumLevel;
            _rootNodes = new QuadtreeNode[_tilingScheme.getRootTilesX() * _tilingScheme.getRootTilesY()];
            for (int j = 0; j < this._tilingScheme.getRootTilesY(); ++j)
            {
                int rowStart = j * this._tilingScheme.getRootTilesX();
                for (int i = 0; i < this._tilingScheme.getRootTilesX(); ++i)
                {
                    QuadtreeTileID id = new QuadtreeTileID(0, i, j);
                    Rectangle extent = tilingScheme.tileToRectangle(id);
                    this._rootNodes[rowStart + i] = new QuadtreeNode(id, extent, null);
                }
            }
        }

        public void addAvailableTileRange(QuadtreeTileRectangularRange range)
        {

        }

        public bool isTileAvailable(QuadtreeTileID id)
        {
            // Get the center of the tile and find the maximum level at that position.
            // Because availability is by tile, if the level is available at that point,
            // it is sure to be available for the whole tile.  We assume that if a tile at
            // level n exists, then all its parent tiles back to level 0 exist too.  This
            // isn't really enforced anywhere, but Cesium would never load a tile for
            // which this is not true.
            Rectangle rectangle = this._tilingScheme.tileToRectangle(id);
            double2 center = rectangle.getCenter();
            return this.computeMaximumLevelAtPosition(center) >= id.level;
        }

        private int computeMaximumLevelAtPosition(double2 position)
        {
            // Find the root node that contains this position.
            foreach (QuadtreeNode pNode in this._rootNodes)
            {
                if (pNode.extent.contains(position))
                {
                    return findMaxLevelFromNode(null, pNode, position);
                }
            }

            return 0;
        }

        private int findMaxLevelFromNode(QuadtreeNode pStopNode, QuadtreeNode pNode, double2 position)
        {
            int maxLevel = 0;
            // Find the deepest quadtree node containing this point.
            bool found = false;
            while (!found)
            {
                int ll = pNode.ll && pNode.ll.extent.contains(position) ? 1 : 0;
                int lr = pNode.lr && pNode.lr.extent.contains(position) ? 1 : 0;
                int ul = pNode.ul && pNode.ul.extent.contains(position) ? 1 : 0;
                int ur = pNode.ur && pNode.ur.extent.contains(position) ? 1 : 0;

                // The common scenario is that the point is in only one quadrant and we can
                // simply iterate down the tree.  But if the point is on a boundary between
                // tiles, it is in multiple tiles and we need to check all of them, so use
                // recursion.
                if (ll + lr + ul + ur > 1)
                {
                    if (ll > 0)
                    {
                        maxLevel = math.max(maxLevel, findMaxLevelFromNode(pNode, pNode.ll, position));
                    }
                    if (lr > 0)
                    {
                        maxLevel = math.max(maxLevel, findMaxLevelFromNode(pNode, pNode.lr, position));
                    }
                    if (ul > 0)
                    {
                        maxLevel = math.max(maxLevel, findMaxLevelFromNode(pNode, pNode.ul, position));
                    }
                    if (ur > 0)
                    {
                        maxLevel = math.max(maxLevel, findMaxLevelFromNode(pNode, pNode.ur, position));
                    }
                    break;
                }
                if (ll > 0)
                {
                    pNode = pNode.ll;
                }
                else if (lr > 0)
                {
                    pNode = pNode.lr;
                }
                else if (ul > 0)
                {
                    pNode = pNode.ul;
                }
                else if (ur > 0)
                {
                    pNode = pNode.ur;
                }
                else
                {
                    found = true;
                }
            }
            // Wal up the tree until we find a rectangle that contains this point.
            while (pNode != pStopNode)
            {
                List<RectangleWithLevel> rectangles = pNode.rectangles;

                // Rectangles are sorted by level, lowest first.
                for (int i = rectangles.Count - 1; i >= 0 && rectangles[i].level > maxLevel; --i)
                {
                    RectangleWithLevel rectangle = rectangles[i];
                    if (rectangle.rectangle.contains(position))
                    {
                        maxLevel = rectangle.level;
                    }
                }

                pNode = pNode.pParent;
            }
            return maxLevel;
        }
    }
}